Computer users seeking to reduce the expense and overhead associated with maintaining their own computing resources have turned to purchasing computing services offered by computing resource service providers. Such computing services are often configurable and scalable to meet various computing needs of the computer users. The use of hosted computing service and storage has proliferated in recent years where the resources for network computing and storage are often provided by computing resource providers that leverage large-scale networks of computer systems to host and execute a variety of applications and services. In such distributed computing systems with multiple distributed data centers, various customers, users, services, and resources of the computing resource service provider can generate frequent modifications to data stored by the computing resource service provider. In such distributed computing systems, it can be difficult to determine the current state of data within distributed storage systems, and even when the state is identified, reliably obtaining and maintaining eventual consistency of the data can be challenging.